package com.vans.practice.alghr;

import java.util.Arrays;

/**
 * @Description: 快速排序
 * @Note: 不稳定啊, 快速排序最重要的是找基准为主， 默认取数组的第一个值为基准比较值
 * @平均时间复杂度： nLog2N
 * @空间复杂度： nLog2N
 * @Author elle
 * @Date 2020/10/6 15:55
 */
public class Quick {

    public static void main(String[] args) {
        int[] a = {9,6,19,11,1,5,10,18};
        sort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }

    private static void sort(int[] a, int from, int to) {
        if (from >= to) return;
        int standard = getStandard(a, from, to);
        //将左右两边的数据再次进行排序
        sort(a, from, standard);
        sort(a, standard +1, to);
    }

    private static int getStandard(int[] a, int from, int to) {
        //取待排序数组的第一个数据作为基准值
        int pivot = a[from];
        while (from < to) {
            while (a[to] > pivot && from < to) to--;
            if (from < to) {
                a[from] = a[to];
            }
            while (a[from] < pivot && from < to) from++;
            if (from < to) {
                a[to] = a[from];
            }
            a[from] = pivot;
        }
        return from;
    }
}
